package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.LinkedList;

public class RecoverBinarySearchTree {

    /**
     * 平衡二叉树的中序遍历为一个升序列表 l，如果有两个节点i, j发生过交换，那么 l[i + 1] < l[i], l[j - 1] > l[j]
     * 所以我们只需要中序遍历树，找到第一个大于后一个元素的元素和最后一个小于前一个元素的元素，然后交换他们的值就行了
     */
    public void recoverTree(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pre = null;
        TreeNode m = null, n = null;
        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && pre.val >= root.val){
                if (m == null){
                    m = pre;
                }
                n = root;
            }
            pre = root;
            root = root.right;
        }
        if (m != null && n != null){
            int t = m.val;
            m.val = n.val;
            n.val = t;
        }
    }


    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(1,3,null,null,2);
        PrintUtils.println(root);
        new RecoverBinarySearchTree().recoverTree(root);
        System.out.println("===========");
        PrintUtils.println(root);
    }

}
